Priority queue, an abstract data type in computer programming is most commonly used in resource allocation for operating systems. Priority queuing has gained industrial importance for communication from back office to front office and for order management systems in manufacturing industries.
It is commonly employed for operating systems in various applications such as telecommunication networks, banking and financial services applications etc.
A typical scheduling system in the current state of art provides priority queuing in First Come First Serve (FCFS) order and thereby provides restrictive serialization, thus lesser priority messages cannot be processed and dispatched in parallel with the high priority messages without restricting the process of the high priority messages.
Another long faced problem in priority scheduling occurs when two high priority messages not related to each other are mapped to the same queue of the processing servers. The typical scheduling system in the current state of art fails to schedule a new process for the second high priority message on any other idle processing servers.
Yet another challenging aspect in priority scheduling of the messages is to provide optimal message load balancing while preserving the serialization constraints for the messages.
Some of the inventions in the current state of art which deals to provide system and methods for priority queue are as follows:
U.S. Pat. No. 7,689,998 to Georgios Chrysanthakopoulos teaches a port-based technique to manage processing resources that can be utilized by an Operating System. Though '998 patent provides priority of a request, which is assumed to be static and known at the time of scheduling, it fails to provide optimal allocation under constraints. Further, '998 patent restricts the assumption for a finite number of priority queues or classes.
U.S. Pat. No. 7,065,766 to Larry Bert Brenner teaches an apparatus and method for load balancing of fixed priority threads in a multiprocessor system. Moreover, '766 patent assumes time slicing and pre-emption of requests in service to deal with load balancing of fixed priority threads across multiple priority queues, where a higher priority thread may displace a lower priority thread. The '766 patent may not be implemented for a serialization constraints associated with at least one thread corresponding to the request class (baseid) and because of time shared implementation the system is not dynamic for plurality of class switching.
U.S. Pat. No. 5,333,319 to Stuart L. Silen teaches a virtual storage data processor for dispatching messages in operating systems for multi programmed data processing systems. The '319 patent maintains common priority of multiple processes serving a given application even if they are across different address spaces; and further deals with serialization through a single threaded execution of a given queue. Though '319 patent teaches improvements in dispatching messages in operating systems for multi programmed data processing systems, it fails to provide optimal load balancing for handling messages of plurality of classes having varied serialization constraints.
U.S. Pat. No. 6,567,840 to Binns et al teaches a method for modeling real-time periodic task scheduling and passing messages within multi task systems. Though '097 patent relates to the area of real time scheduling under deadlines where priority depends on the application characteristics and is inversely proportional to deadline, it fails to discuss about scheduling messages with priority under serialization constraints and optimality of load balancing.
U.S. Pat. No. 4,794,926 to Munsch et al teaches a microcomputer comprising memory and a process which is arranged to execute a plurality of concurrent processes and share its time between them. Though '097 patent discusses about scheduling of processes within a single processor with static priorities attached to each process, it fails to discuss scheduling of process with multiprocessor and dynamic priorities and further does not discuss about elements of serialization.
In light of the above mentioned prior arts it is evident that the current state of art restricts the scheduling of processes within a single multiprocessor having static priorities rather than a multiprocessor with dynamic priorities.
Hence there is a need in the art for a customizable solution for:
1. Prioritizing the scheduling of plurality of messages belonging to plurality of classes based on desired scheduling requirements of a front office system.
2. Achieving optimal load balancing for handling a burst of messages while preserving the serialization constraints.